package org.hhchat.leetcode.dp;

/**
 * Created this one by HMH on 2017/6/12.
 */
public class code343 {
    public class Solution {
        public int integerBreak(int n) {
            if(n==2) return 1;
            if(n==3) return 2;
            int product = 1;
            while(n>4){
                product*=3;
                n-=3;
            }
            product*=n;

            return product;
        }
    }
}

//DP method

//    public int integerBreak(int n) {
//        int[] dp = new int[n + 1];
//        dp[1] = 1;
//        for(int i = 2; i <= n; i ++) {
//            for(int j = 1; j < i; j ++) {
//                dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
//            }
//        }
//        return dp[n];
//    }